/*
https://leetcode.cn/problems/number-of-2s-in-range-lcci/submissions/568324898/
面试题 17.06. 2出现的次数
*/
class Solution {
public:
    int numberOf2sInRange(int n) {
        string s = to_string(n);
        int m = s.length(),dp[m][m];
        memset(dp,-1,sizeof(dp));
        auto dfs = [&](auto&& dfs, int i, int two, bool is_limit) -> int {
            if (i == m) {       
                return two; // is_num 为 true 表示得到了一个合法数字
            }
            if (!is_limit && dp[i][two] != -1) {
                return dp[i][two];   //算过了就直接将它返回
            }
            //res存储答案
            int res = 0;
            int up = is_limit ? s[i] - '0' : 9;
            int d = 0;
            for (; d <= up; d++) {
            res += dfs(dfs, i + 1,two+(d==2), is_limit && d == up);
            }
            if (!is_limit) {
                dp[i][two] = res; // 记忆化
            }
            return res;
        };
        return dfs(dfs, 0, 0, true);
    }
};